package NC91_最长上升子序列3;

import java.util.*;


public class Solution {
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型一维数组 the array
     * @return int整型一维数组
     */
    public int[] LIS (int[] arr) {
        // write code here
        int[] dp = new int[arr.length];
        // 初始化 为1
        for (int i = 0; i < arr.length; i++){
            dp[i] = 1;
        }

        int maxN = 0;
        for (int i = 1; i < arr.length - 1; i++){
            // 找到满足 j < i，arr[j] < arr[i],的最大 dp[j] 进行转移
            int res = 0;
            for (int j = 0; j < i; j++){
                if (arr[i] > arr[j]){
                    res = Math.max(res, dp[j]);
                }
            }
            dp[i] = res + 1;    // 加上 arr[i]
            maxN = Math.max(maxN, dp[i]);   // 找到最大长度
        }

        int[] ans = new int[maxN];
        for (int i = arr.length - 1, j = maxN;j > 0; i--){
            // 逆向找到第一个满足所需大小的数
            if (dp[i] == j){
                ans[--j] = arr[i];  // 填入后继续寻找下一个数
            }
        }
        return ans;
    }
}